<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,100分)- 猜数字（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>一个人设定一组四码的数字作为谜底&#xff0c;另一方猜。</p> 
<p>每猜一个数&#xff0c;出数者就要根据这个数字给出提示&#xff0c;提示以XAYB形式呈现&#xff0c;直到猜中位置。</p> 
<p>其中X表示位置正确的数的个数&#xff08;数字正确且位置正确&#xff09;&#xff0c;而Y表示数字正确而位置不对的数的个数。</p> 
<p>例如&#xff0c;当谜底为8123&#xff0c;而猜谜者猜1052时&#xff0c;出题者必须提示0A2B。</p> 
<p>例如&#xff0c;当谜底为5637&#xff0c;而猜谜者才4931时&#xff0c;出题者必须提示1A0B。</p> 
<p>当前已知N组猜谜者猜的数字与提示&#xff0c;如果答案确定&#xff0c;请输出答案&#xff0c;不确定则输出NA。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行输入一个正整数&#xff0c;0&#xff1c;N &#xff1c; 100。</p> 
<p>接下来N行&#xff0c;每一行包含一个猜测的数字与提示结果。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出最后的答案&#xff0c;答案不确定则输出NA。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">6<br /> 4815 1A1B<br /> 5716 0A1B<br /> 7842 0A1B<br /> 4901 0A0B<br /> 8585 3A0B<br /> 8555 2A1B</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3585</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>我的解题思路是&#xff1a;</p> 
<p>暴力枚举所有可能的谜底&#xff0c;即0000~9999&#xff0c;然后用每一个谜底去过输入的猜测。</p> 
<p>我们假设某个谜底 和 输入的猜测数字 产生的猜测提示是real_result&#xff0c;而输入中猜测数字对应的猜测提示是expect_result&#xff0c;如果real_result &#61;&#61; expect_result&#xff0c;那么说明说明当前谜底符合当前猜测数字的要求。</p> 
<p>如果某个谜底&#xff0c;可以符合所有猜测数字的要求&#xff0c;那么该谜底就是一个可用谜底。</p> 
<p>如果&#xff0c;暴力枚举出来的所有谜底中&#xff0c;只有一个可用谜底&#xff0c;那么该谜底就是题解。否则本题无解&#xff0c;返回NA。</p> 
<p></p> 
<p>当前上面算法非常容易超时&#xff0c;原因就是我们需要验证0000~9999这一万个可能的谜底&#xff0c;而每个可能的谜底有需要验证最多100个输入的猜测数字。</p> 
<p>因此&#xff0c;我们需要做一些剪枝优化&#xff0c;比如题目用例输入中有一行&#xff1a;</p> 
<blockquote> 
 <p>4901 0A0B</p> 
</blockquote> 
<p>这行的含义其实是&#xff1a;真正的谜底的四个数字不能取4&#xff0c;9&#xff0c;0&#xff0c;1这些。</p> 
<p>再比如&#xff1a;</p> 
<blockquote> 
 <p>5716 0A1B<br /> 7842 0A1B<br /> 4901 0A0B</p> 
</blockquote> 
<p>上面三行中&#xff0c;都是0A&#xff0c;即每一位上的数字都不是真正谜底的该位置的数字。</p> 
<p>比如&#xff1a;5716 0A1B</p> 
<p>即&#xff1a;真正的谜底&#xff0c;第一位不可能是5&#xff0c;第二位不可能是7&#xff0c;第三位不可能是1&#xff0c;第四位不可能是6</p> 
<p>那么真正的谜底&#xff0c;第一位只能从非5数种选&#xff0c;第二位只能从非7数中选.......</p> 
<p>这样的话&#xff0c;就做到了剪枝优化&#xff0c;即四码谜底的每一位数不需要从0~9中选&#xff0c;而是可以从更小的范围内选。</p> 
<p>目前&#xff0c;我这边制作了0A&#xff0c;以及0A0B的剪枝处理&#xff0c;其他情况比如&#xff1a;</p> 
<p>0A0B  0A1B  0A2B  0A3B  0A4B<br /> 1A0B  1A1B  1A2B  1A3B<br /> 2A0B  2A1B  2A2B<br /> 3A0B  3A1B<br /> 4A0B</p> 
<p>可以视实际机试时间限制要求选做。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n;
let infos;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61; 1) {
    n &#61; lines[0] - 0;
  }

  if (n &amp;&amp; lines.length &#61;&#61; n &#43; 1) {
    lines.shift();
    infos &#61; lines.map((line) &#61;&gt; line.split(&#34; &#34;));
    console.log(getResult());
    lines.length &#61;&#61; 0;
  }
});

function getResult() {
  const num &#61; getCombine();
  const cache &#61; [];

  for (let c1 of num[0]) {
    for (let c2 of num[1]) {
      for (let c3 of num[2]) {
        for (let c4 of num[3]) {
          const answer &#61; &#96;${c1}${c2}${c3}${c4}&#96;;
          if (isValid(answer)) cache.push(answer);
        }
      }
    }
  }

  // 答案不确定则输出NA
  if (cache.length !&#61; 1) return &#34;NA&#34;;
  else return cache[0];
}

// 剪枝逻辑&#xff0c;本题的后期优化主要在这个方法内进行
// 返回的是一个集合&#xff0c;集合有四个元素&#xff0c;分别对应四码的谜底数字的每一位&#xff0c;而每个集合元素又是一个Set&#xff0c;里面存放谜底数字对应的位上可能是哪些数字
function getCombine() {
  // 初始时&#xff0c;四码谜底的每一位都有十种可能&#xff0c;即每一位都能取值0~9
  const num &#61; new Array(4)
    .fill(0)
    .map(() &#61;&gt; new Set(new Array(10).fill(0).map((_, i) &#61;&gt; i &#43; &#34;&#34;)));

  // 遍历猜谜者猜的数字guess_num与提示guess_result
  for (let info of infos) {
    const [guess_num, guess_result] &#61; info;

    // 数字正确且位置正确的个数
    let countA &#61; guess_result[0] - 0;
    // 数字正确而位置不对的数的个数
    let countB &#61; guess_result[2] - 0;

    // 如果countA &#61;&#61; 0,则说明当前guess_num的每一位上的数字的位置都不正确&#xff0c;即对应位上不应该出现对应数字
    if (countA &#61;&#61; 0) {
      for (let i &#61; 0; i &lt; 4; i&#43;&#43;) {
        const c &#61; guess_num[i];
        // 如果countB &#61;&#61; 0&#xff0c;则说明当前guess_num上所有位上的数字都不正确&#xff0c;即任意位上都不应该出现该数字
        if (countB &#61;&#61; 0) {
          num[0].delete(c);
          num[1].delete(c);
          num[2].delete(c);
          num[3].delete(c);
        } else {
          num[i].delete(c);
        }
      }
    }
  }

  return num;
}

// 判断谜底answer是否正确&#xff0c;即是否符合所有猜测提示
function isValid(answer) {
  for (let info of infos) {
    const [guess, expect_result] &#61; info;
    const real_result &#61; getGuessResult(guess, answer);
    if (real_result !&#61; expect_result) return false;
  }
  return true;
}

// 获取猜的数字guess在指定谜底answer下的猜测提示
function getGuessResult(guess, answer) {
  let countA &#61; 0;
  let countB &#61; 0;

  const answer_arr &#61; new Array(10).fill(0);
  const guess_arr &#61; new Array(10).fill(0);

  for (let i &#61; 0; i &lt; guess.length; i&#43;&#43;) {
    const c1 &#61; guess[i] - 0;
    const c2 &#61; answer[i] - 0;

    if (c1 &#61;&#61; c2) countA&#43;&#43;;
    else {
      guess_arr[c1]&#43;&#43;;
      answer_arr[c2]&#43;&#43;;
    }
  }

  for (let i &#61; 0; i &lt; 10; i&#43;&#43;) {
    countB &#43;&#61; Math.min(answer_arr[i], guess_arr[i]);
  }

  return &#96;${countA}A${countB}B&#96;;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.*;

public class Main {
  static String[][] infos;

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    infos &#61; new String[n][2];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      infos[i][0] &#61; sc.next();
      infos[i][1] &#61; sc.next();
    }

    System.out.println(getResult());
  }

  public static String getResult() {
    ArrayList&lt;HashSet&lt;Character&gt;&gt; num &#61; getCombine();
    ArrayList&lt;String&gt; cache &#61; new ArrayList&lt;&gt;();

    for (Character c1 : num.get(0)) {
      for (Character c2 : num.get(1)) {
        for (Character c3 : num.get(2)) {
          for (Character c4 : num.get(3)) {
            String answer &#61; new String(new char[] {c1, c2, c3, c4});
            if (isValid(answer)) {
              cache.add(answer);
            }
          }
        }
      }
    }

    // 答案不确定则输出NA
    if (cache.size() !&#61; 1) return &#34;NA&#34;;
    else return cache.get(0);
  }

  // 剪枝逻辑&#xff0c;本题的后期优化主要在这个方法内进行
  // 返回的是一个集合&#xff0c;集合有四个元素&#xff0c;分别对应四码的谜底数字的每一位&#xff0c;而每个集合元素又是一个Set&#xff0c;里面存放谜底数字对应的位上可能是哪些数字
  public static ArrayList&lt;HashSet&lt;Character&gt;&gt; getCombine() {
    List&lt;Character&gt; tmp &#61; Arrays.asList(&#39;0&#39;, &#39;1&#39;, &#39;2&#39;, &#39;3&#39;, &#39;4&#39;, &#39;5&#39;, &#39;6&#39;, &#39;7&#39;, &#39;8&#39;, &#39;9&#39;);
    ArrayList&lt;HashSet&lt;Character&gt;&gt; num &#61; new ArrayList&lt;&gt;();
    // 初始时&#xff0c;四码谜底的每一位都有十种可能&#xff0c;即每一位都能取值0~9
    for (int i &#61; 0; i &lt; 4; i&#43;&#43;) num.add(new HashSet&lt;&gt;(tmp));

    // 将infos按照猜测提示进行字典序升序&#xff0c;即0A0B排在最前面&#xff0c;4A0B排在最后面&#xff0c;这样排序的用意是0A0B可以不依赖其他条件完成数字过滤
    //    Arrays.sort(infos, (a, b) -&gt; a[1].compareTo(b[1]));

    // 遍历猜谜者猜的数字guess_num与提示guess_result
    for (String[] info : infos) {
      String guess_num &#61; info[0];
      String guess_result &#61; info[1];

      // 数字正确且位置正确的个数
      int countA &#61; guess_result.charAt(0) - &#39;0&#39;;
      // 数字正确而位置不对的数的个数
      int countB &#61; guess_result.charAt(2) - &#39;0&#39;;

      // 如果countA &#61;&#61; 0,则说明当前guess_num的每一位上的数字的位置都不正确&#xff0c;即对应位上不应该出现对应数字
      if (countA &#61;&#61; 0) {
        for (int i &#61; 0; i &lt; 4; i&#43;&#43;) {
          Character c &#61; guess_num.charAt(i);
          if (countB &#61;&#61; 0) {
            // 如果countB &#61;&#61; 0&#xff0c;则说明当前guess_num上所有位上的数字都不正确&#xff0c;即任意位上都不应该出现该数字
            num.get(0).remove(c);
            num.get(1).remove(c);
            num.get(2).remove(c);
            num.get(3).remove(c);
          } else {
            num.get(i).remove(c);
          }
        }
      }
    }

    return num;
  }

  // 判断谜底answer是否正确&#xff0c;即是否符合所有猜测提示
  public static boolean isValid(String answer) {
    for (String[] info : infos) {
      String guess &#61; info[0];
      String expect_result &#61; info[1];
      String real_result &#61; getGuessResult(guess, answer);
      if (!expect_result.equals(real_result)) return false;
    }
    return true;
  }

  // 获取猜的数字guess在指定谜底answer下的猜测提示
  public static String getGuessResult(String guess, String answer) {
    int countA &#61; 0;
    int countB &#61; 0;

    int[] answer_arr &#61; new int[10];
    int[] guess_arr &#61; new int[10];

    for (int i &#61; 0; i &lt; guess.length(); i&#43;&#43;) {
      char c1 &#61; guess.charAt(i);
      char c2 &#61; answer.charAt(i);

      if (c1 &#61;&#61; c2) countA&#43;&#43;;
      else {
        answer_arr[c2 - &#39;0&#39;]&#43;&#43;;
        guess_arr[c1 - &#39;0&#39;]&#43;&#43;;
      }
    }

    for (int i &#61; 0; i &lt; 10; i&#43;&#43;) {
      countB &#43;&#61; Math.min(answer_arr[i], guess_arr[i]);
    }

    return new StringBuilder().append(countA).append(&#34;A&#34;).append(countB).append(&#34;B&#34;).toString();
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
n &#61; int(input())
infos &#61; [input().split() for _ in range(n)]


# 获取猜的数字guess在指定谜底answer下的猜测提示
def getGuessResult(guess, answer):
    countA &#61; 0
    countB &#61; 0

    answer_arr &#61; [0] * 10
    guess_arr &#61; [0] * 10

    for i in range(len(guess)):
        c1 &#61; int(guess[i])
        c2 &#61; int(answer[i])

        if c1 &#61;&#61; c2:
            countA &#43;&#61; 1
        else:
            guess_arr[c1] &#43;&#61; 1
            answer_arr[c2] &#43;&#61; 1

    for i in range(10):
        countB &#43;&#61; min(answer_arr[i], guess_arr[i])

    return f&#34;{countA}A{countB}B&#34;


# 判断谜底answer是否正确&#xff0c;即是否符合所有猜测提示
def isValid(answer):
    for info in infos:
        guess, expect_result &#61; info
        real_result &#61; getGuessResult(guess, answer)
        if expect_result !&#61; real_result:
            return False
    return True


# 剪枝逻辑&#xff0c;本题的后期优化主要在这个方法内进行
# 返回的是一个列表&#xff0c;列表有四个元素&#xff0c;分别对应四码的谜底数字的每一位&#xff0c;而每个列表元素又是一个列表&#xff0c;里面存放谜底数字对应的位上可能是哪些数字
def getCombine():
    # 初始时&#xff0c;四码谜底的每一位都有十种可能&#xff0c;即每一位都能取值0~9
    num &#61; [set([i for i in range(10)]) for _ in range(4)]

    # 遍历猜谜者猜的数字guess_num与提示guess_result
    for info in infos:
        guess_num, guess_result &#61; info

        # 数字正确且位置正确的个数
        countA &#61; int(guess_result[0])
        # 数字正确而位置不对的数的个数
        countB &#61; int(guess_result[2])

        # 如果countA &#61;&#61; 0,则说明当前guess_num的每一位上的数字的位置都不正确&#xff0c;即对应位上不应该出现对应数字
        if countA &#61;&#61; 0:
            for i in range(4):
                c &#61; int(guess_num[i])
                if countB &#61;&#61; 0:
                    # 如果countB &#61;&#61; 0&#xff0c;则说明当前guess_num上所有位上的数字都不正确&#xff0c;即任意位上都不应该出现该数字
                    num[0].discard(c)
                    num[1].discard(c)
                    num[2].discard(c)
                    num[3].discard(c)
                else:
                    num[i].discard(c)

    return num


# 算法入口
def getResult():
    num &#61; getCombine()
    cache &#61; []

    for c1 in num[0]:
        for c2 in num[1]:
            for c3 in num[2]:
                for c4 in num[3]:
                    answer &#61; f&#34;{c1}{c2}{c3}{c4}&#34;
                    if isValid(answer):
                        cache.append(answer)

    # 答案不确定则输出NA
    if len(cache) !&#61; 1:
        return &#34;NA&#34;
    else:
        return cache[0]


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>